Выпуклая оптимизация: Определение стандартной формы выпуклой задачи

Задача выпуклой оптимизации в стандартной форме является основой современного математического программирования. Она определяется выпуклой целевой функцией $f_0$, выпуклыми неравенствами $f_i$ и аффинными равенствами. Определив задачу на пересечении этих областей $\mathcal{D} = \bigcap_{i=0}^m \text{dom } f_i$, мы гарантируем, что любое локальное оптимальное решение является глобальным.

1. Математическая структура стандартной формы

Задача формально формулируется следующим образом:

$$\begin{aligned} &\text{минимизировать} && f_0(x) \\ &\text{при условии} && f_i(x) \leq 0, \quad i = 1, \dots, m \\ &&& a_i^T x = b_i, \quad i = 1, \dots, p \end{aligned}$$

Допустимое множество определяется как $\text{dom } F = \{x \in \text{dom } f_0 \mid f_i(x) \le 0, i = 1, \dots, m, h_i(x) = 0, i = 1, \dots, p \}$. Критическое требование для выпуклости заключается в том, что равенства должны быть аффинными ($Ax = b$), поскольку нелинейные равенства обычно приводят к невыпуклым множествам.

2. Геометрическая интерпретация эпиграфа

Эта задача в форме эпиграфа позволяет нам геометрически интерпретировать оптимизацию в «пространстве графика» $(x, t)$. Введя переменную-дополнение $t$, мы минимизируем $t$ при условии $(x, t) \in \text{epi } f_0$. Это показывает, что допустимое множество, любое подуровневое множество и оптимальное множество являются по своей сути выпуклыми.

3. Ошибка скрытых (неявных) против явных ограничений

Распространённое заблуждение состоит в том, что перенос ограничений в целевую функцию (сделав их неявными) упрощает задачу. Однако, сделать ограничения неявными не сделало задачу проще для анализа или решения, даже если результатом становится задача с номинально отсутствующими ограничениями. Это особенно верно в случае модели оракула (черного ящика), где мы вычисляем $f(x)$ и её производные с определённой стоимостью, не зная явной структуры функции.

4. Применение в реальном мире

Теория портфеля: Минимизация риска $\text{var}(c^T x) = x^T \Sigma x$ для 4 активов (например, Актив 1 с доходностью 12% / стандартным отклонением 20%).
Инженерные задачи: Структурные ограничения, такие как $y_i = 6(i - 1/3) \frac{F}{E w_i h_i^3} + v_{i+1} + y_{i+1}$.
Теория вероятностей: Ограничения на риск потерь $\Phi^{-1}(\beta) \leq 0$.

🎯 Основной принцип

Условие оптимальности для дифференцируемой функции $f_0$ задается как $\nabla f_0(x)^T(y - x) \geq 0$ для всех допустимых $y$. Это означает, что градиент должен быть опорной гиперплоскостью для допустимого множества в оптимальной точке.

ВОПРОС 1

Почему равенства в задаче выпуклой оптимизации должны быть аффинными ($Ax = b$)?

Потому что нелинейные равенства обычно определяют невыпуклые множества.

Чтобы гарантировать, что целевая функция остаётся дифференцируемой.

Потому что модель оракула не может обрабатывать нелинейные подпрограммы.

Чтобы позволить использовать переменные-дополнения для преобразования неравенств.

ВОПРОС 2

В модели оракула (черного ящика), какой из следующих вариантов верен?

Вычисление целевой функции не требует вычислительных затрат.

Явная структура функции неизвестна, но мы можем вычислять $f(x)$ и её производные.

Неявные ограничения делают задачу значительно проще для решения, чем явные.

Матрица Ханкеля должна быть диагональной для сходимости модели.

ВОПРОС 3

Что представляет собой эпиграф выпуклой функции $f_0$ в контексте оптимизации?

Множество всех точек, где градиент равен нулю.

Множество точек, лежащих на графике функции или выше его.

Пересечение всех аффинных равенств.

Линейная комбинация мономов с вещественными коэффициентами.

ВОПРОС 4

Какое математическое условие представляет собой спектральное ограничение на матрицу $A$, ограниченную значением $s$?

$\|A\|_2 \leq s \iff A^T A \preceq s^2 I$

$Ax = b$

$\text{var}(c^T x) = x^T \Sigma x$

$\Phi^{-1}(\beta) \leq 0$

ВОПРОС 5

Каков результат введения переменных-дополнений для неравенства $f_i(x) \le 0$?

Задача становится безограниченной.

Он заменяет неравенство равенством и ограничением неотрицательности.

Он преобразует выпуклую задачу в невыпуклую сигномиальную задачу.

Допустимое множество проектируется на матрицу Ханкеля.

Вызов: Преобразование задачи и векторная оптимальность

Часть А: Геометрическое программирование (GP)
Рассмотрим задачу оптимизации:
максимизировать $x/y$
при условии: $2 \le x \le 3$, $x^2 + 3y/z \le \sqrt{y}$, и $x/y = z^2$.
Ваша задача — преобразовать эту задачу в эквивалентную стандартную форму GP (минимизация позинома).

Часть Б: Парето-оптимальность
Предположим, у нас есть векторная задача оптимизации с целевой функцией $f_0$. Мы заменяем $f_0$ на $\phi \circ f_0$, где $\phi$ строго $K$-монотонна ($u \preceq_K v, u \neq v \implies \phi(u) \preceq_K \phi(v)$). Докажите эквивалентность точек Парето-оптимальности.

1. Предоставьте стандартную форму GP для Части А.

Чтобы максимизировать $x/y$, мы минимизируем моном $(x/y)^{-1} = x^{-1}y$. Ограничения должны иметь вид позинома $\le 1$ и монома $= 1$.
- Цель: $\text{минимизировать } x^{-1}y$
- О1: $2x^{-1} \le 1$
- О2: $(1/3)x \le 1$
- О3: $x^2 y^{-1/2} + 3y^{1/2}z^{-1} \le 1$ (разделив на $\sqrt{y}$)
- О4: $xy^{-1}z^{-2} = 1$
Все переменные $x, y, z > 0$.

2. Решите оптимальность для двумерной задачи: минимизируйте $f_0(x_1, x_2) = x_1 + x_2$ при условиях $2x_1 + x_2 \ge 1, x_1 + 3x_2 \ge 1, x_1, x_2 \ge 0$. Каково оптимальное значение?

Вершины допустимой области: $(0, 1)$, $(1, 0)$ и пересечение $2x_1 + x_2 = 1$ и $x_1 + 3x_2 = 1$. Решая систему: $x_1 = 2/5, x_2 = 1/5$.
Вычисляем $f_0 = x_1 + x_2$:
- В точке $(0, 1): 1$
- В точке $(1, 0): 1$
- В точке $(2/5, 1/5): 3/5$
Оптимальное значение: $3/5$ в точке $x^* = (0.4, 0.2)$.